package com.xie.leetcode.list;

import com.xie.leetcode.base.ListNode;

//19. 删除链表的倒数第 N 个结点
//        给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
//        示例 1：
//
//        输入：head = [1,2,3,4,5], n = 2
//        输出：[1,2,3,5]
//        示例 2：
//
//        输入：head = [1], n = 1
//        输出：[]
//        示例 3：
//
//        输入：head = [1,2], n = 1
//        输出：[1]
//
//        提示：
//
//        链表中结点的数目为 sz
//        1 <= sz <= 30
//        0 <= Node.val <= 100
//        1 <= n <= sz

/**
 * @author xiezhendong
 * @date 2021/10/23
 */
public class RemoveNthFromEnd {

    public static void main(String[] args) {
        RemoveNthFromEnd removeNthFromEnd = new RemoveNthFromEnd();
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        System.out.println(removeNthFromEnd.removeNthFromEnd(node1, 2));
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode resNode = new ListNode(0, head);
        int length = this.getLength(head);
        ListNode cur = resNode;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return resNode.next;
    }

    private int getLength(ListNode head) {
        int length = 1;
        ListNode nextNode = head.next;
        while (nextNode != null) {
            length++;
            nextNode = nextNode.next;
        }
        return length;
    }
}
